2.5 Map的工作原理
map基本在每一种编程语言中都存在，并且他们的实现方式也是大同小异，底层原理也是有一些共通之处。
本节将针对map的底层实现、性能优化等方面进行一个详细的讲解。在学习本节前，如果对哈希表还不了解，建议先去看一下哈希表的知识。
本节代码存放目录为 lesson5
底层实现结构
在Go语言中，map的底层实现是基于哈希表的。map结构是一个复杂且高度优化的数据结构，它主要通过哈希表实现键值对的存储和快速查找。
在底层实现上，是由一个叫做hmap的结构体表示的。结构如下所示：
// A header for a Go map.
type hmap struct {
count int // map 中存储的键值对的数量
flags uint8
B uint8 // 当前桶数组的大小是 2^B
noverflow uint16 // 溢出桶的数量
hash0 uint32 // 哈希种子，用于计算哈希值
buckets unsafe.Pointer // 指向桶数组的指针
oldbuckets unsafe.Pointer // 扩展过程中用于保存旧的桶数组
nevacuate uintptr // 搬迁进度指针，记录扩展过程中迁移的数据位置
extra *mapextra // 一些额外的信息（可选，用于优化）
}
在上面的结构中，可以看到其包含了哈希表的元数据、哈希种子、桶数组等数据。接下来我们分别说一下每个字段到底是干什么的。
count：用于跟踪map中的元素数量，这个值在插入、删除操作时会动态更新。它也可以用于计算
map的负载因子（即count除以桶的数量），以决定何时触发扩展操作。flags：这是一个标志位，用于存储一些与map状态相关的标志信息。比如当前是否在搬迁中、是否只读、是否在迭代中等。B：这个字段控制了map的桶数量。因为桶的数量始终是2的幂，所以使用B来表示。比如：如果
B是 5，那么桶的数量就是2^5 = 32。noverflow：用于记录发生哈希冲突所导致的溢出桶的数量，主要用于性能度量，通过这个字段可以知道map的效率、当前哈希冲突的状况等。hash0：为了防止哈希碰撞攻击，Go语言在计算哈希值时使用了一个随机生成的种子值hash0。这意味着每次运行程序时，键相同的
map可能会在不同的位置存储数据。buckets：这是map的核心数据结构，它指向存储键值对的桶数组。桶数组的大小由
B控制，buckets指向数组的起始地址。通过哈希函数计算出的哈希值，使用该指针定位到具体的桶。
oldbuckets：这个字段主要用于map扩展时使用。当map扩展时，需要增加桶的数量以减少哈希冲突。在这个过程中，
map会同时维护两个桶数组：一个是扩展前的旧桶数组（由oldbuckets指向），另一个是扩展后的新桶数组（由buckets指向）。旧的桶数组会逐步被搬迁到新桶数组，而不是一次性完成，从而避免了性能瓶颈。
nevacuate：为了避免扩展map时的一次性开销，Go语言采用了渐进式搬迁策略。每次访问
map时，都会搬迁一部分旧桶中的数据到新桶。nevacuate记录了搬迁的进度，确保扩展是逐步完成的。它主要指示了当前已经搬迁到哪个桶。
extra：这是一个指向mapextra结构的指针，用于存储一些额外的信息，以优化性能。extra并不是所有map都需要的，当map使用某些高级特性时，比如需要更复杂的溢出桶管理或保存更多的搬迁信息时，extra才会被使用。
总的来说，map的底层就是通过哈希表来实现的，通过结构体与哈希表结合，实现了键值对map。至于更底层的扩展、溢出其实可以不用太关注了，与原本哈希的概念差不多。
我们以一段代码来看一下底层的数据，代码如下所示：
// hmap 结构
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra unsafe.Pointer
}
// 通过反射和 unsafe 获取底层结构
func inspectMap(m interface{}) {
// 通过反射获取 map 的指针
val := reflect.ValueOf(m)
mapValue := (*hmap)(unsafe.Pointer(val.Pointer()))
// 打印 hmap 结构的各个字段
fmt.Printf("Count: %d\n", mapValue.count)
fmt.Printf("Flags: %d\n", mapValue.flags)
fmt.Printf("B: %d (number of buckets: %d)\n", mapValue.B, 1<<mapValue.B)
fmt.Printf("Noverflow: %d\n", mapValue.noverflow)
fmt.Printf("Hash0: %d\n", mapValue.hash0)
fmt.Printf("Buckets: %v\n", mapValue.buckets)
fmt.Printf("Oldbuckets: %v\n", mapValue.oldbuckets)
fmt.Printf("Nevacuate: %d\n", mapValue.nevacuate)
fmt.Printf("Extra: %v\n", mapValue.extra)
}
aMap := make(map[int]int)
aMap[1] = 100
aMap[2] = 200
inspectMap(aMap)
结果输出如下所示：
Count: 2
Flags: 0
B: 0 (number of buckets: 1)
Noverflow: 0
Hash0: 254814633
Buckets: 0x14000028090
Oldbuckets: <nil>
Nevacuate: 0
Extra: <nil>
工作原理
map的工作原理其实与哈希表本身的概念是相结合的，都是基于哈希表的特性来进行的。
我们以一段代码来做说明，看一下这一段代码执行时都做了哪些事情。代码如下所示：
var (
bMap map[int]int
)
bMap = make(map[int]int)
fmt.Printf("current len-> %d\n", len(bMap))
bMap[1] = 1
fmt.Printf("current len-> %d\n", len(bMap))
delete(bMap, 1)
fmt.Printf("current len-> %d\n", len(bMap))
声明与初始化
var ( aMap map[int]int ) aMap = make(map[int]int)使用
var声明时仅仅只是声明了一个map类型的变量，此时是没有分配内存，没有初始化的，aMap的值也为nil。使用
make进行了aMap的初始化，此时就会为底层的hmap分配内存，初始化相关的字段。需要注意的是，此时底层的桶数组其实还是
nil，只有在第一次插入数据时才会初始化。检查长度
fmt.Printf("current len-> %d\n", len(aMap))这里其实与我们之前讲到的切片是有相似之处的，都是直接获取了底层结构的
count字段进行展示。
插入键值对
aMap[1] = 1首先
Go会计算键1的哈希值，使用hash0作为种子，将1转换为一个哈希值。由于这是第一次插入，
buckets仍然为nil。这时候就会根据B的值（此时B = 0）分配一个最小的桶数组（大小为2^B = 1个桶）。下一步哈希值通过
mod运算确定要存储的桶索引，这时候桶数组的大小为1，所有键值对都会落在同一个桶内。完成数据存储后，下一步会更新
hmap内的count计数，进行加一操作。删除键值对
delete(aMap, 1)首先会通过键
1再次计算哈希值，之后通过哈希值找到所在的桶。之后会在桶中找到相应的位置，将数据标记为删除，同时
hmap的count执行减一操作。
通过上面的代码分析，我们可以看到map在进行操作时遵循底层哈希表的规则。分别执行了哈希值计算、查找桶、添加数据、更新数量等操作。
小结
本节我们讲解了map的底层结构以及工作时的操作步骤。
关于本节总结如下：
map的底层结构是哈希表底层同样是数组的概念来进行的
通过哈希表实现了数据的高效查找及添加